package pers.qianyu.month_202101.date_20210112;

import pers.qianyu.util.model.*;

import java.util.*;
import java.util.stream.*;

/**
 * 257. 二叉树的所有路径
 * https://leetcode-cn.com/problems/binary-tree-paths/
 *
 * @author mizzle rain
 * @date 2021-01-12 17:14
 */
public class BinaryTreePaths {
    public List<String> binaryTreePaths(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<String> res = new ArrayList<>();
        ArrayList<Integer> path = new ArrayList<>();
        path.add(root.val);
        backTracking(res, path, root);
        return res;
    }

    private void backTracking(List<String> res, ArrayList<Integer> path, TreeNode root) {
        if (root.left == null && root.right == null) {
            res.add(path.stream().map(String::valueOf).collect(Collectors.joining("->")));
            return;
        }
        if (root.left != null) {
            path.add(root.left.val);
            backTracking(res, path, root.left);
            path.remove(path.size() - 1);
        }
        if (root.right != null) {
            path.add(root.right.val);
            backTracking(res, path, root.right);
            path.remove(path.size() - 1);
        }
    }
}
